package n1276;

import java.util.Scanner;

public class Main {

	
	static int f[]=new int[100001];
	
	static int packCount,cash,N;
	
	static void zeroOnePack(int weight,int cost)
	{
		for(int j=cash;j>=cost;j--)
		{
			if(f[j]<f[j-cost]+weight)f[j]=f[j-cost]+weight;
		}
	}
	
	static void completePack(int weight,int cost)
	{
		for(int j=cost;j<=cash;j++)
		{
			if(f[j]<f[j-cost]+weight)f[j]=f[j-cost]+weight;
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception{
		Scanner cin=new Scanner(System.in);
		while(cin.hasNext())
		{
				cash=cin.nextInt();
				N=cin.nextInt();
				packCount=0;
				for(int i=0;i<N;i++)
				{
					int nk=cin.nextInt();
					int dk=cin.nextInt();
					if(nk*dk>=cash)
					{
						completePack(dk, dk);
					}else {
						for(int k=1;k<nk;k*=2) {
							int weight=k*dk;
							zeroOnePack(weight, weight);
							nk-=k;
						}
						zeroOnePack(nk*dk, nk*dk);
					}
				}
				System.out.println(f[cash]);
				for(int i=0;i<cash+1;i++)f[i]=0;
		}
	}

}
